home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / kernel / mem / memory.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-12-19  |  44.8 KB  |  1,611 lines
  1. /*
  2.  *  memory.c --
  3.  *
  4.  *    This file implements a dynamic memory allocation system.
  5.  *    It provides procedures to allocate and release storage,
  6.  *    and also includes monitoring and tracing features.
  7.  *
  8.  * Copyright 1985 Regents of the University of California
  9.  * All rights reserved.
  10.  */
  11.  
  12. #ifndef lint
  13. static char rcsid[] = "$Header: /cdrom/src/kernel/Cvsroot/kernel/mem/memory.c,v 9.6 91/09/10 18:40:12 rab Exp $ SPRITE (Berkeley)";
  14. #endif /* not lint */
  15.  
  16.  
  17. #include <stdlib.h>
  18. #include <mem.h>
  19. #include <memInt.h>
  20. #include <sprite.h>
  21. #include <sync.h>
  22. #include <stdio.h>
  23. #undef free
  24.  
  25. extern void _free _ARGS_((Address blockPtr));
  26.  
  27. /*
  28.  * If the MEM_TRACE flag is defined, extra code will be compiled to allow
  29.  * programs to trace Mem_Alloc and Mem_Free calls.
  30. #define MEM_TRACE
  31.  */
  32.  
  33. /*
  34.  * WARNING: several of the macros in this file expect both integers and
  35.  * pointers to be 32 bits (4 bytes) long.
  36.  */
  37.  
  38. /*
  39.  * This storage allocator consists of two independent allocators,
  40.  * one used for binned objects (<= BIN_SIZE bytes) and the other
  41.  * used for large objects.
  42.  *
  43.  * Both allocators deal with "blocks" of storage, which correspond
  44.  * roughly to the areas that users request and free.  Each block of
  45.  * storage consists of one administrative word followed by the
  46.  * useable area.  All allocations are done in even numbers of words,
  47.  * which means that clients may occasionally get more bytes than
  48.  * they asked for.  Mem_Alloc returns the address of the word just
  49.  * after the administrative word.  The administrative word allows us
  50.  * to keep track of which blocks are in use and which are free, and also
  51.  * keeps track of the sizes of blocks so clients don't have to know how
  52.  * large a block is when they free it.  The low-order bit of the
  53.  * administrative word indicates whether or not the block is free, and
  54.  * the rest of the word tells how large the block is (in bytes
  55.  * including the administrative word).  The next-to-low-order bit
  56.  * of each block is used to indicate that this is a "dummy block"(see
  57.  * the comments for the large-object allocator).  Using the low-order
  58.  * bits for flags works because all blocks that we allocate are always
  59.  * multiples of 4 bytes in length.  There is one exception to this
  60.  * usage of the administrative word, which occurs for free binned objects.
  61.  * In this case the word is a link to the next free binned object instead
  62.  * of a size.  The macros below define the format of the administrative
  63.  * words and how to access them.
  64.  *
  65.  * All objects <= SMALL_SIZE are automatically binned.  In order to bin
  66.  * objects between SMALL_SIZE and BIN_SIZE bytes the routine Mem_Bin
  67.  * should be called.  Note that Mem_Bin must be called before any objects
  68.  * of the size to be binned have been allocated.
  69.  */
  70.  
  71. #ifdef MEM_TRACE
  72.  
  73. typedef struct {
  74.     int        admin;        /* Administrative word. */
  75.     Address    pc;        /* PC of call to Mem_Alloc. */
  76.     int        origSize;    /* Original size given to Mem_Alloc. */
  77.     int         padding;    /* To make it double word aligned */
  78. } AdminInfo;
  79.  
  80. #define GET_ADMIN(blockPtr)    (((AdminInfo *) (blockPtr))->admin)
  81. #define SET_ADMIN(blockPtr, value)  \
  82.             ((AdminInfo *) (blockPtr))->admin = (int) (value)
  83.  
  84. #define GET_PC(blockPtr)    (((AdminInfo *) (blockPtr))->pc)
  85. #define SET_PC(blockPtr)    ((AdminInfo *) (blockPtr))->pc = Mem_CallerPC()
  86.  
  87. #define GET_ORIG_SIZE(blockPtr)    (((AdminInfo *) (blockPtr))->origSize)
  88. #define SET_ORIG_SIZE(blockPtr,size)    \
  89.             ((AdminInfo *) (blockPtr))->origSize = size
  90.  
  91. #else /* MEM_TRACE */
  92. #if defined(sequent)
  93.  
  94. /*
  95.  * Need 16-byte alignment for Sequent Symmetry due to various IO devices
  96.  * (eg, SCED needs 8-byte alignment, DCC needs 16-byte).  Would be nicer if
  97.  * all upper level code doing IO insured the buffers were aligned (hence avoid
  98.  * extra fragmentation here), but will live with this.  Note that this isn't a
  99.  * problem in Sequent Dynix, since all IO buffers are implicitly aligned.
  100.  *
  101.  * Note that can probably align the bin'd objects differently so that the
  102.  * admin word lives just before a 16-byte boundary.  This is more than I want
  103.  * to modify right now ;-)
  104.  *
  105.  * This assumes Vm_RawAlloc() returns 16-byte aligned data, as well.
  106.  */
  107.  
  108. typedef struct {
  109.     int        admin;        /* Administrative word. */
  110.     int         padding[3];    /* To make it 16-byte aligned */
  111. } AdminInfo;
  112.  
  113. #define GET_ADMIN(blockPtr)    (((AdminInfo *) (blockPtr))->admin)
  114. #define SET_ADMIN(blockPtr, value)  \
  115.             ((AdminInfo *) (blockPtr))->admin = (int) (value)
  116. #else   /* sequent */            
  117. typedef double AdminInfo;
  118.  
  119. #define GET_ADMIN(blockPtr)    (*(int *)(AdminInfo *) (blockPtr))
  120. #define SET_ADMIN(blockPtr, value) *((int *)(AdminInfo *) (blockPtr)) = (int) (value)
  121. #endif /* sequent */
  122. #endif /* MEM_TRACE */
  123.  
  124. #define USE_BIT        1
  125. #define DUMMY_BITS    3
  126. #define ADMIN_BITS(admin)    ((admin) & DUMMY_BITS)
  127. #define IS_IN_USE(admin)    ((admin) & USE_BIT)
  128. #define IS_DUMMY(admin)        (((admin) & DUMMY_BITS) == DUMMY_BITS)
  129. #define MARK_DUMMY(admin)    ((admin) | DUMMY_BITS)
  130. #define MARK_IN_USE(admin)    ((admin) | USE_BIT)
  131. #define MARK_FREE(admin)    ((admin) & ~DUMMY_BITS)
  132. #define SIZE(admin)        ((admin) & ~DUMMY_BITS)
  133.  
  134. /*
  135.  * The memory manager is a monitor.  The following definition is
  136.  * for its monitor lock.
  137.  */
  138.  
  139. static Sync_Lock memMonitorLock = Sync_LockInitStatic("memMonitorLock");
  140. #define LOCKPTR (&memMonitorLock)
  141.  
  142. static int mem_NumAllocs = 0;
  143. static int mem_NumFrees = 0;
  144.  
  145. #define    MAX_TO_PRINT    256
  146. static struct {
  147.     int        size;        /* Size of the block. */
  148.     int        num;        /* Number of blocks allocated. */
  149.     int        free;        /* Number of blocks freed. */
  150.     int        inUse;        /* Number of blocks still in use. */
  151.     int        dummy;        /* Number of blocks used as dummy blocks. */
  152. } topN[MAX_TO_PRINT + 1];
  153.  
  154. static void Init _ARGS_((void));
  155.  
  156. #ifdef MEM_TRACE
  157. INTERNAL static void PrintTrace _ARGS_((Boolean allocated,
  158.     register Address infoPtr, Address curPC));
  159. INTERNAL static void DoTrace _ARGS_((Boolean allocated,
  160.     register Address infoPtr, Address curPC, int size));
  161. #endif
  162.  
  163. /*
  164.  * ----------------------------------------------------------------------------
  165.  *
  166.  *    Binned-object allocator: it keeps a separate linked free list
  167.  *    for each size of object less than SMALL_SIZE bytes in size and
  168.  *    a free list for all objects less than BIN_SIZE that have been
  169.  *    specified as being binned by a call to Mem_Bin.
  170.  *    The blocks on each list are linked together via their
  171.  *    administrative words, terminated by a NIL pointer.  Allocation
  172.  *    and freeing are done in a stack-like manner from the front of
  173.  *    the free lists.
  174.  *
  175.  *    Definitions (these are all related:  if you change one, you'll
  176.  *    have to change several):
  177.  *
  178.  *    GRANULARITY: The difference in size between succesive buckets.  This
  179.  *        is determined by data alignment restrictions and should be
  180.  *        a power of 2 to allow for shifting to map from size to bucket.
  181.  *    SIZE_SHIFT: The shift distance to convert between size and bucket.
  182.  *    SMALL_SIZE: largest blocksize (total including administrative word)
  183.  *        managed by default by the binned-object allocator.  This
  184.  *        should be 1 less than a multiple of the granularity.
  185.  *    BIN_SIZE: largest possible that can be binned.  Should be one less
  186.  *        than a multiple of the granularity.
  187.  *
  188.  *    These can be computed from the above constants.
  189.  *
  190.  *    SMALL_BUCKETS: default number of separate free lists.
  191.  *    BIN_BUCKETS: number of binned free lists.
  192.  *    BYTES_TO_BLOCKSIZE: how many bytes a block must contain (total
  193.  *        including admin. word) to satisfy a user request in bytes.
  194.  *    BLOCKSIZE_TO_INDEX: which free list to use for blocks of a given
  195.  *        size (total including administrative word).
  196.  *    INDEX_TO_BLOCKSIZE: the (maximum) size corresponding to a bucket.
  197.  *        This will include the size of the administrative word.
  198.  *
  199.  *    These constants determine how many new blocks are allocated to
  200.  *        a bin at one time.
  201.  *
  202.  *    MIN_BLOCKS_AT_ONCE: The amount allocate the first time, and the amount
  203.  *        to increment the number of blocks each successive time.
  204.  *    MIN_SHIFT: The log2 of MIN_BLOCKS_AT_ONCE.
  205.  *    MAX_BLOCKS_AT_ONCE: the most number of blocks to be allocated at once.
  206.  *
  207.  * ----------------------------------------------------------------------------
  208.  */
  209.  
  210. #if defined(sequent)
  211.  
  212. /*
  213.  * 16 byte alignment to for Sequent Symmetry.  Making granularity also 16
  214.  * bytes has nice cache effects (at least thru Model B; this isn't
  215.  * functionally important, but it may affect performance).
  216.  */
  217. #define GRANULARITY            16
  218. #define SIZE_SHIFT            4
  219.  
  220. /*
  221.  * This SMALL_SIZE determined by examination of memory tracing, 1/89.
  222.  * The BIN_SIZE allows us to bin an FS_BLOCK_SIZE object.
  223.  */
  224. #define SMALL_SIZE            271
  225. #define    BIN_SIZE            4207
  226.  
  227. #else    /* sequent */
  228.  
  229. /*
  230.  * 8 byte granularity to handle SPUR and SPARC.
  231.  */
  232. #define GRANULARITY            8
  233. #define SIZE_SHIFT            3
  234. /*
  235.  * This SMALL_SIZE determined by examination of memory tracing, 1/89.
  236.  * The BIN_SIZE allows us to bin an FS_BLOCK_SIZE object.
  237.  */
  238. #define SMALL_SIZE            271
  239. #define    BIN_SIZE            4199
  240.  
  241. #endif /* sequent */ 
  242.  
  243. #define SMALL_BUCKETS            ((SMALL_SIZE + 1) / GRANULARITY)
  244. #define BIN_BUCKETS            ((BIN_SIZE + 1) / GRANULARITY)
  245. #define MASK                (GRANULARITY - 1)
  246. #define BYTES_TO_BLOCKSIZE(bytes) ((bytes+MASK+sizeof(AdminInfo)) & (~MASK))
  247. #define BLOCKSIZE_TO_INDEX(size)  ((size) >> SIZE_SHIFT)
  248. #define INDEX_TO_BLOCKSIZE(index) ((index) << SIZE_SHIFT)
  249. /*
  250.  * These are set up to allocate 4, 8, 12, and then 16 blocks at a time.
  251.  */
  252. #define MIN_BLOCKS_AT_ONCE        4
  253. #define MIN_SHIFT            2
  254. #define MAX_BLOCKS_AT_ONCE         16
  255.  
  256. /*
  257.  * The following array holds pointers to the first free blocks of each size.
  258.  * Bucket i holds blocks whose total length is INDEX_TO_BLOCKSIZE(i) bytes
  259.  * (including the administrative info).  Blocks from bucket i are used to
  260.  * satisfy user requests ranging from INDEX_TO_BLOCKSIZE(i)-sizeof(AdminInfo)
  261.  * bytes up to INDEX_TO_BLOCKSIZE(i)-1 bytes.
  262.  * Buckets 0 and 1 are never used, since they correspond to blocks too small
  263.  * to hold any information for the user.
  264.  */
  265.  
  266. static Address freeLists[BIN_BUCKETS];
  267.  
  268. /*
  269.  * Used to gather statistics about allocations:
  270.  */
  271.  
  272. static int numBlocks[BIN_BUCKETS];    /* Total number of existing blocks,
  273.                      * both allocated and free, for each
  274.                      * small size.  */
  275. static int numAllocs[BIN_BUCKETS];    /* Total number of allocation requests
  276.                      * made for blocks of each small size.
  277.                      */
  278.  
  279. /*
  280.  * ----------------------------------------------------------------------------
  281.  *    Large-object allocator:  used for blocks that aren't binned.
  282.  *    We expect there to be relatively few allocations
  283.  *    made by the large-object allocator.  Since all the blocks it
  284.  *    allocates are relatively large, fragmentation should be less
  285.  *    than it would be if it allocated small blocks too. All of the
  286.  *    blocks, in use or not, are kept in a single linked list using
  287.  *    their administrative words.  The address of the next block in
  288.  *    the list is found by adding the size of the current block to the
  289.  *    address of its administrative word.  Things are complicated
  290.  *    slightly because the storage area managed by this allocator
  291.  *    may be discontiguous:  there could be several large regions
  292.  *    that it manages, separated by gaps that are managed by some other
  293.  *    storage allocator (e.g. the binned-object allocator).  In this
  294.  *    case, the gaps between regions are handled by making the gaps
  295.  *    look like allocated blocks, with an administrative word at the
  296.  *    end of one region that causes a skip to the beginning of the
  297.  *    next region.  These blocks are called "dummy blocks", and have
  298.  *    special flag bits in their administrative words (see definitions
  299.  *    below).  All the blocks within a region are linked together
  300.  *    in increasing order of address.  However, the different regions
  301.  *    may appear in any order on the list.  Two dummy blocks mark the
  302.  *    beginning and end of the list.
  303.  * ----------------------------------------------------------------------------
  304.  */
  305.  
  306. static char *first, *last;
  307. static char _first[sizeof(AdminInfo) + 4], _last[sizeof(AdminInfo) + 4];
  308.                 /* Dummy blocks marking beginning and
  309.                  * end of free list.  Last has a size of
  310.                  * zero.  */
  311. static Address currentPtr;    /* Next block to consider allocating.
  312.                  * Rotates circularly through free list. */
  313. int largestFree;        /* This holds the size of the largest
  314.                  * free block that's been seen on the
  315.                  * free list.  It's updated as the
  316.                  * list is traversed.  */
  317.  
  318. /*
  319.  * Minimum size of new regions requested by large-object allocator
  320.  * when storage runs out:
  321.  */
  322.  
  323. #define MIN_REGION_SIZE 2048
  324.  
  325. static int numLargeBytes;    /* Total amount of storage managed by
  326.                  * the large allocator.  */
  327. static int numLargeAllocs;    /* Total number of allocation requests
  328.                  * handled by the large allocator.  */
  329. static int numLargeLoops;    /* Number of iterations through the
  330.                  * inner block-checking loop of the
  331.                  * large allocator.  */
  332.  
  333. /*
  334.  * ----------------------------------------------------------------------------
  335.  *    Miscellaneous declarations.
  336.  * ----------------------------------------------------------------------------
  337.  */
  338.  
  339. /*
  340.  * Flag to make sure Init gets called once.
  341.  */
  342.  
  343. static void    Init _ARGS_((void));
  344. static int    initialized = FALSE;
  345.  
  346.  
  347. #ifdef MEM_TRACE
  348.  
  349. /*
  350.  * When Mem_Alloc or Mem_Free is called, a trace record will be printed and/or
  351.  * the number of blocks being used by the caller will be stored in the trace
  352.  * array if the block size is in sizeTraceArray. The array is defined with
  353.  * Mem_SetTraceSizes(). PrintTrace calls a default printing routine; it can
  354.  * be changed with Mem_SetPrintProc().
  355.  */
  356. #define MAX_NUM_TRACE_SIZES    20
  357. #define    MAX_CALLERS_TO_TRACE    20
  358. static    struct TraceElement {
  359.     Mem_TraceInfo    traceInfo;
  360.     struct {
  361.     Address    callerPC;
  362.     int    numBlocks;
  363.     } allocInfo[MAX_CALLERS_TO_TRACE];
  364. } sizeTraceArray[MAX_NUM_TRACE_SIZES];
  365.  
  366. static    int    numSizesToTrace = 0;
  367.  
  368. int        mem_PrintLargeAllocPC = 0;
  369.  
  370. #endif /* MEM_TRACE */
  371.  
  372.  
  373.  
  374. /*
  375.  * ----------------------------------------------------------------------------
  376.  *
  377.  * Init --
  378.  *
  379.  *      Initializes the dynamic storage allocator.
  380.  *
  381.  * Results:
  382.  *      None.
  383.  *
  384.  * Side effects:
  385.  *      The storage allocation structures are initialized.
  386.  *
  387.  * ----------------------------------------------------------------------------
  388.  */
  389.  
  390. INTERNAL static void
  391. Init()
  392. {
  393.     int i;
  394.  
  395.     /*
  396.      * Clear out all of the bins.
  397.      */
  398.     for (i = BIN_BUCKETS - 1; i > SMALL_BUCKETS - 1; i--) {
  399.     numBlocks[i] = -1;
  400.     freeLists[i] = (Address) NIL;
  401.     numAllocs[i] = 0;
  402.     }
  403.  
  404.     /*
  405.      * Clear out the small-object free lists.
  406.      */
  407.     for (; i >= 0; i--) {
  408.     freeLists[i] = (Address) NIL;
  409.     numBlocks[i] = 0;
  410.     numAllocs[i] = 0;
  411.     }
  412.  
  413.     /*
  414.      * Initialize the large-object free list with two dummy blocks that
  415.      * mark its beginning and end. These blocks are declared to be arrays
  416.      * of characters. In order for malloc to work correctly they have to
  417.      * be aligned on word boundaries.
  418.      */
  419. #if 0
  420.     if (((int) first) & 0x3) {
  421.     panic("Mem: 'first' is not word-aligned");
  422.     }
  423.     if (((int) last) & 0x3) {
  424.     panic("Mem: 'last' is not word-aligned");
  425.     }
  426. #else
  427.     first = (char *) (((long)_first + 3) & ~3);
  428.     last = (char *) (((long)_last + 3) & ~3);
  429. #endif
  430.  
  431.     SET_ADMIN(first, MARK_DUMMY(last-first));
  432.     SET_ADMIN(last, MARK_DUMMY(0));
  433.     currentPtr        = first;
  434.     largestFree        = 0;
  435.     numLargeBytes    = 0;
  436.     numLargeAllocs    = 0;
  437.     numLargeLoops    = 0;
  438.  
  439.     MemPrintInit();
  440. }
  441.  
  442. /*
  443.  * ----------------------------------------------------------------------------
  444.  *
  445.  * Mem_Bin --
  446.  *
  447.  *    Make objects of the given size be binned.
  448.  *
  449.  * Results:
  450.  *    None.
  451.  *
  452.  * Side effects:
  453.  *    The bin corresponding to blocks of the given size is initialized.
  454.  *
  455.  * ----------------------------------------------------------------------------
  456.  */
  457. ENTRY void
  458. Mem_Bin(numBytes)
  459.     int    numBytes;
  460. {
  461.     int    index;
  462.  
  463.     LOCK_MONITOR;
  464.  
  465.     if (!initialized) {
  466.         initialized = TRUE;
  467.     Init();
  468.     }
  469.     if (mem_NumAllocs > 0) {
  470.     MemPanic("Mem_Bin: Mem_Alloc already called.\n");
  471.     }
  472.     numBytes = BYTES_TO_BLOCKSIZE(numBytes);
  473.     if (numBytes > BIN_SIZE) {
  474.     UNLOCK_MONITOR;
  475.     return;
  476.     }
  477.     index = BLOCKSIZE_TO_INDEX(numBytes);
  478.     if (numBlocks[index] >= 0) {
  479.     UNLOCK_MONITOR;
  480.     return;
  481.     }
  482.     numBlocks[index] = 0;
  483.  
  484.     UNLOCK_MONITOR;
  485. }
  486.  
  487.  
  488. /*
  489.  * ----------------------------------------------------------------------------
  490.  *
  491.  * malloc --
  492.  *
  493.  *    This procedure allocates a chunk of memory.
  494.  *
  495.  * Results:
  496.  *    The return value is a pointer to an area of at least numBytes
  497.  *    bytes of free storage.  If no memory is available, then this
  498.  *    procedure will never return:  the MemChunkAlloc procedure
  499.  *    determines what will happen.
  500.  *
  501.  * Side effects:
  502.  *    The returned block is marked as allocated and will not be
  503.  *    allocated to anyone else until it is returned with a call
  504.  *    to free().
  505.  *
  506.  * ----------------------------------------------------------------------------
  507.  */
  508.  
  509.  
  510. ENTRY Address
  511. malloc(numBytes)
  512.     register unsigned int numBytes;    /* How many bytes to allocate.
  513.                      *    Must be > 0 */
  514. {
  515.     register int size, admin;
  516.     Address    result;
  517.     Address    newRegion;
  518.     int        regionSize;
  519. #ifdef MEM_TRACE
  520.     int        origSize;
  521. #endif /* MEM_TRACE */
  522.     register int index;
  523.  
  524.     LOCK_MONITOR;
  525.  
  526.  
  527.     mem_NumAllocs++;
  528.  
  529.     if (!initialized) {
  530.         initialized = TRUE;
  531.     Init();
  532.     }
  533.  
  534. #ifdef MEM_TRACE
  535.     origSize = numBytes;
  536. #endif /* MEM_TRACE */
  537.  
  538.     /*
  539.      * Handle binned objects quickly, if possible.
  540.      */
  541.     numBytes = BYTES_TO_BLOCKSIZE(numBytes);
  542.     index = BLOCKSIZE_TO_INDEX(numBytes);
  543.     if (numBytes <= BIN_SIZE && numBlocks[index] != -1) {
  544.     if (freeLists[index] == (Address) NIL) {
  545.         register int blocksAtOnce;
  546.  
  547.         /*
  548.          * There aren't currently any free objects of this size.
  549.          * Call the client's function to obtain another region
  550.          * from the system.  While we're at it, get a whole bunch
  551.          * of objects of this size once and put all but one back
  552.          * on the free list.
  553.          */
  554.         if (numBlocks[index] < MAX_BLOCKS_AT_ONCE) {
  555.         blocksAtOnce = ((numBlocks[index] >> MIN_SHIFT) + 1) *
  556.                 MIN_BLOCKS_AT_ONCE;
  557.         } else {
  558.         blocksAtOnce = MAX_BLOCKS_AT_ONCE;
  559.         }
  560.         regionSize = MemChunkAlloc(blocksAtOnce * numBytes, &newRegion);
  561.  
  562.         while (regionSize >= numBytes) {
  563.         SET_ADMIN(newRegion, freeLists[index]);
  564.         freeLists[index] = newRegion;
  565.         numBlocks[index] += 1;
  566.         newRegion += numBytes;
  567.         regionSize -= numBytes;
  568.         }
  569.  
  570.         /*
  571.          * If we were given more bytes than we wanted, and there aren't
  572.          * quite enough left to make a full block, put the leftovers
  573.          * on the free list for the smallest size.  This may still result
  574.          * in GRANULARITY bytes leftover that we have to throw away.
  575.          */
  576.  
  577.         while (regionSize >= (sizeof(AdminInfo) + GRANULARITY)) {
  578.         SET_ADMIN(newRegion, freeLists[2]);
  579.         freeLists[2] = newRegion;
  580.         numBlocks[2] += 1;
  581.         newRegion += (sizeof(AdminInfo) + GRANULARITY);
  582.         regionSize -= (sizeof(AdminInfo) + GRANULARITY);
  583.         }
  584.     }
  585.  
  586.     result = freeLists[index];
  587.     freeLists[index] = (Address) GET_ADMIN(result);
  588.     SET_ADMIN(result, MARK_IN_USE(numBytes));
  589.     numAllocs[index] += 1;
  590.  
  591. #ifdef MEM_TRACE
  592.     SET_PC(result);
  593.     SET_ORIG_SIZE(result, origSize);
  594.     DoTrace(TRUE, result, (Address)NULL, numBytes);
  595. #endif /* MEM_TRACE */
  596.  
  597.     UNLOCK_MONITOR;
  598.     return(result+sizeof(AdminInfo));
  599.     }
  600.  
  601.     /*
  602.      * This is a large object.  Step circularly through the blocks
  603.      * in the list, looking for one that's large enough to hold
  604.      * what's needed.  Move currentPtr to the next block in the list to
  605.      * make sure that we make forward progress each time Mem_Alloc is called.
  606.      * If we don't then there is an instability in the memory allocator
  607.      * with the following pattern:
  608.      *
  609.      *  while (TRUE) {
  610.      *        addr = malloc(4096);
  611.      *      free(addr);
  612.      *      malloc(248);
  613.      *  }
  614.      *
  615.      * This pattern causes memory to get heavily fragmented.
  616.      */
  617.  
  618.     numLargeAllocs += 1;
  619.     admin = GET_ADMIN(currentPtr);
  620.     currentPtr += SIZE(admin);
  621.     while (TRUE) {
  622.     Address nextPtr;
  623.  
  624.     numLargeLoops += 1;
  625.     admin = GET_ADMIN(currentPtr);
  626.     size = SIZE(admin);
  627.     nextPtr = currentPtr+size;
  628.     if (!IS_IN_USE(admin)) {
  629.     
  630.         /*
  631.          * Several blocks in a row could have been freed since the last
  632.          * time we were here.  If so, merge them together.
  633.          */
  634.  
  635.         while (!IS_IN_USE(GET_ADMIN(nextPtr))) {
  636.         size += SIZE(GET_ADMIN(nextPtr));
  637.         admin = MARK_FREE(size);
  638.         SET_ADMIN(currentPtr, admin);
  639.         nextPtr = currentPtr+size;
  640.         }
  641.         if (size >= numBytes) {
  642.         break;
  643.         }
  644.         if (size > largestFree) {
  645.         largestFree = size;
  646.         }
  647.     }
  648.  
  649.     /*
  650.      * This block won't do the job.  Go on to the next block.
  651.      * If the next block is the end of the list, then go back
  652.      * to the beginning and start again, unless no storage has
  653.      * been freed since the last time we went back.  In this
  654.      * case, allocate a new region of storage.
  655.      */
  656.     
  657.     if (nextPtr != last) {
  658.         currentPtr = nextPtr;
  659.         continue;
  660.     }
  661.  
  662.     if (largestFree > numBytes) {
  663.         largestFree = 0;
  664.         currentPtr = first;
  665.         continue;
  666.     }
  667.  
  668.     if (numBytes < MIN_REGION_SIZE) {
  669.         regionSize = MemChunkAlloc(MIN_REGION_SIZE, &newRegion);
  670.     } else {
  671.         regionSize = MemChunkAlloc(numBytes + sizeof(AdminInfo),
  672.                            &newRegion);
  673.     }
  674.     numLargeBytes += regionSize;
  675.  
  676.     /*
  677.      * If the new region immediately follows the end of the previous
  678.      * region, merge the two together (at this point currentPtr always
  679.      * points to a dummy block whose administrative word points to "last").
  680.      * If we can't merge, then make currentPtr link to the new area.
  681.      */
  682.  
  683.     if (newRegion == (currentPtr+sizeof(AdminInfo))) {
  684.         newRegion = currentPtr;
  685.         regionSize += sizeof(AdminInfo);
  686.     } else {
  687.         SET_ADMIN(currentPtr, MARK_DUMMY(newRegion - currentPtr));
  688.     }
  689.  
  690.     /*
  691.      * Create a dummy block at the end of the new region, which links
  692.      * to "last".
  693.      */
  694.     
  695.     SET_ADMIN(newRegion, MARK_FREE(regionSize - sizeof(AdminInfo)));
  696.     newRegion += regionSize - sizeof(AdminInfo);
  697.     SET_ADMIN(newRegion, MARK_DUMMY(last - newRegion));
  698.  
  699.     /*
  700.      * Continue scanning the list (try currentPtr again in case it
  701.      * merged with the new region).
  702.      */
  703.     }
  704.  
  705.     /*
  706.      * At this point we've got a block that's large enough.  If it's
  707.      * larger than needed for the object, put the rest back on the
  708.      * free list (note: even if the remnant is smaller than the smallest
  709.      * large object, which means it'll be used by itself, we put it back
  710.      * on the list so it can merge with either this block or the next,
  711.      * whichever gets freed first).
  712.      */
  713.  
  714.     if (size == numBytes) {
  715.     SET_ADMIN(currentPtr, MARK_IN_USE(admin));
  716.     } else {
  717.     SET_ADMIN(currentPtr+numBytes, MARK_FREE(size-numBytes));
  718.     SET_ADMIN(currentPtr, MARK_IN_USE(numBytes));
  719.     }
  720.  
  721. #ifdef MEM_TRACE
  722.     SET_PC(currentPtr);
  723.     SET_ORIG_SIZE(currentPtr, origSize);
  724.     DoTrace(TRUE, currentPtr, (Address)NULL, numBytes);
  725. #endif /* MEM_TRACE */
  726.  
  727.     result = currentPtr;
  728.     UNLOCK_MONITOR;
  729.     return(result+sizeof(AdminInfo));
  730. }
  731.  
  732.  
  733. /*
  734.  * ----------------------------------------------------------------------------
  735.  *
  736.  * _free --
  737.  *
  738.  *      Return a previously-allocated block of storage to the free pool.
  739.  *
  740.  * Results:
  741.  *      None.
  742.  *
  743.  * Side effects:
  744.  *      The storage pointed to by blockPtr is marked as free and returned
  745.  *    to the free pool.  Nothing in the bytes pointed to by blockPtr is
  746.  *    modified at this time:  no change will occur until at least the
  747.  *    next call to Mem_Alloc.  This means that callers may use the contents
  748.  *    of a block for a short time after free-ing it (e.g. to read a
  749.  *    "next" pointer).
  750.  *
  751.  * ----------------------------------------------------------------------------
  752.  */
  753.  
  754. ENTRY int
  755. free(blockPtr) 
  756.     Address blockPtr;
  757. {
  758.      _free(blockPtr);
  759.     return 0;
  760. }
  761.  
  762. ENTRY void
  763. _free(blockPtr)
  764.     Address blockPtr;       /* Pointer to storage to be freed.  Must
  765.                  * have been the return value from Mem_Alloc
  766.                  * at some previous time.  */
  767. {
  768.     register int  admin;
  769.     register int  index;
  770.     register int  size;
  771.  
  772.     LOCK_MONITOR;
  773.  
  774.     mem_NumFrees++;
  775.  
  776.     if (!initialized) {
  777.         MemPanic("Mem_Free: allocator not initialized!\n");
  778.     return;        /* should never get here */
  779.     }
  780.  
  781.     /*
  782.      *  Make sure that this block bears some resemblance to a
  783.      *  well-formed storage block.
  784.      */
  785.  
  786.     blockPtr -= sizeof(AdminInfo);
  787.     admin = GET_ADMIN(blockPtr);
  788.     if (ADMIN_BITS(admin) != USE_BIT) {
  789.     if (!IS_IN_USE(admin)) {
  790.         if (!memAllowFreeingFree) {
  791.         MemPanic("Mem_Free: storage block already free\n");
  792.         }
  793.     } else {
  794.         MemPanic("Mem_Free: storage block is corrupted\n");
  795.     }
  796.     UNLOCK_MONITOR;
  797.     return;            /* (should never get here) */
  798.     }
  799.  
  800.     /* This procedure is easier for large blocks than for small ones.
  801.      * If large, just clear the use bit.  Since this block could merge
  802.      * with its neighbors, we don't really know anymore what's the
  803.      * largest size on the free list, so set largestFree to a very
  804.      * large number.  This guarantees that the allocator will check
  805.      * the whole list again before requesting additional memory.
  806.      */
  807.  
  808.     size = SIZE(admin);
  809.     index = BLOCKSIZE_TO_INDEX(size);
  810.     if (size > BIN_SIZE || numBlocks[index] == -1) {
  811.     SET_ADMIN(blockPtr, MARK_FREE(admin));
  812.     largestFree = numLargeBytes;
  813.     } else {
  814.     /*
  815.      * For small blocks, add the block back onto its free list.
  816.      */
  817.  
  818.     SET_ADMIN(blockPtr, freeLists[index]);
  819.     freeLists[index] = blockPtr;
  820.     }
  821.  
  822. #ifdef MEM_TRACE
  823.     DoTrace(FALSE, blockPtr, Mem_CallerPC(), size);
  824. #endif /* MEM_TRACE */
  825.  
  826.     UNLOCK_MONITOR;
  827.     return;
  828. }
  829.  
  830. /*
  831.  * Global variables that can be set to control thresholds for printing
  832.  * statistics.
  833.  */
  834.  
  835. static int mem_SmallMinNum = 1;         /* There must be at least this many
  836.                                          * binned objects of a size before info
  837.                                          * about its size gets printed. */
  838. static int mem_LargeMinNum  = 1;        /* There must be at least this many
  839.                                          * non-binned objects of a size before
  840.                                          * info about the size gets printed. */
  841. static int mem_LargeMaxSize = 10000;    /* Info is printed for non-binned
  842.                                          * objects larger than this regardless
  843.                                          * of how many of them there are. */
  844.  
  845. /*
  846.  * ----------------------------------------------------------------------------
  847.  *
  848.  * Mem_Size --
  849.  *
  850.  *      Return the size of a previously-allocated storage block.
  851.  *
  852.  * Results:
  853.  *      The return value is the size of *blockPtr, in bytes.  This is
  854.  *    the total usable size of the block.  It may be slightly greater
  855.  *    than the size actually requested in the Mem_Alloc, since this
  856.  *    module rounds sizes up to convenient boundaries.
  857.  *
  858.  * Side effects:
  859.  *    None.
  860.  *
  861.  * ----------------------------------------------------------------------------
  862.  */
  863.  
  864. ENTRY int
  865. Mem_Size(blockPtr)
  866.     Address blockPtr;    /* Pointer to storage to be freed.  Must have been the
  867.              * return value from Mem_Alloc at some previous time. */
  868. {
  869.     int admin;
  870.  
  871.     LOCK_MONITOR;
  872.  
  873.     if (!initialized) {
  874.         MemPanic("Mem_Size: allocator not initialized!\n");
  875.     UNLOCK_MONITOR;
  876.     return(0);            /* should never get here */
  877.     }
  878.  
  879.     /*
  880.      *  Make sure that this block bears some resemblance to a
  881.      *  well-formed storage block.
  882.      */
  883.     
  884.     blockPtr -= sizeof(AdminInfo);
  885.     admin = GET_ADMIN(blockPtr);
  886.     if (ADMIN_BITS(admin) != USE_BIT) {
  887.     if (!IS_IN_USE(admin)) {
  888.         MemPanic("Mem_Size: storage block is free\n");
  889.     } else {
  890.         MemPanic("Mem_Size: storage block is corrupted\n");
  891.     }
  892.     UNLOCK_MONITOR;
  893.     return(0);            /* (should never get here) */
  894.     }
  895.  
  896.     UNLOCK_MONITOR;
  897.     return(SIZE(admin) - sizeof(AdminInfo));
  898. }
  899.  
  900.  
  901. /*
  902.  *----------------------------------------------------------------------
  903.  *
  904.  * Mem_PrintStats --
  905.  *
  906.  *    Print out memory statistics with Mem_PrintStatsSubr using the
  907.  *    default printing routine and default sizes.
  908.  *
  909.  *    See Mem_PrintStatsSubrInt for details.
  910.  *
  911.  * Results:
  912.  *    None.
  913.  *
  914.  * Side effects:
  915.  *    None.
  916.  *
  917.  *----------------------------------------------------------------------
  918.  */
  919. ENTRY void
  920. Mem_PrintStats()
  921. {
  922.     LOCK_MONITOR;
  923.  
  924.     Mem_PrintStatsSubrInt(memPrintProc, memPrintData, mem_SmallMinNum,
  925.               mem_LargeMinNum, mem_LargeMaxSize);
  926.  
  927.     UNLOCK_MONITOR;
  928. }
  929.  
  930.  
  931. /*
  932.  *----------------------------------------------------------------------
  933.  *
  934.  * Mem_PrintStatsInt --
  935.  *
  936.  *    Print out memory statistics with Mem_PrintStatsSubr using the
  937.  *    default printing routine and default sizes.  Same as Mem_PrintStats
  938.  *    except that this routine does not grab the monitor lock.  This is
  939.  *    intended to be used to print out memory stats when the operating
  940.  *    system runs out of memory after being called by Mem_Alloc and hence
  941.  *    the monitor is already down.
  942.  *
  943.  *    See Mem_PrintStatsSubrInt for details.
  944.  *
  945.  * Results:
  946.  *    None.
  947.  *
  948.  * Side effects:
  949.  *    None.
  950.  *
  951.  *----------------------------------------------------------------------
  952.  */
  953. void
  954. Mem_PrintStatsInt()
  955. {
  956.     Mem_PrintStatsSubrInt(memPrintProc, memPrintData, mem_SmallMinNum,
  957.               mem_LargeMinNum, mem_LargeMaxSize);
  958. }
  959.  
  960.  
  961. /*
  962.  * ----------------------------------------------------------------------------
  963.  *
  964.  * Mem_PrintStatsSubr --
  965.  *
  966.  *      This procedure prints out statistics about memory allocation
  967.  *    so far.  Grabs monitor lock and calls the unmonitored routine
  968.  *    Mem_PrintStatsSubrInt.
  969.  *
  970.  * Results:
  971.  *      None.
  972.  *
  973.  * Side effects:
  974.  *      None.
  975.  *
  976.  * ----------------------------------------------------------------------------
  977.  */
  978. ENTRY void
  979. Mem_PrintStatsSubr(printProc, clientData, smallMinNum, largeMinNum,
  980.     largeMaxSize)
  981.     void     (*printProc)();    /* Procedure to actually print stuff. */
  982.     ClientData    clientData;    /* Argument to pass to printProc. */
  983.     int        smallMinNum;    /* Minimum number of elements in a bucket
  984.                  * before will print out stats. */
  985.     int        largeMinNum;    /* Minimum number of large objects of a given
  986.                  * size before will print out stats about
  987.                  * the size. */
  988.     int        largeMaxSize;    /* Statistics will be printed about all blocks
  989.                  * over size regardless of how many there are*/
  990. {
  991.     LOCK_MONITOR;
  992.  
  993.     Mem_PrintStatsSubrInt(printProc, clientData, smallMinNum, largeMinNum,
  994.               largeMaxSize);
  995.  
  996.     UNLOCK_MONITOR;
  997. }
  998.  
  999.  
  1000. /*
  1001.  * ----------------------------------------------------------------------------
  1002.  *
  1003.  * Mem_PrintConfig --
  1004.  *
  1005.  *      Prints out the exact configuration of the dynamic memory allocator
  1006.  *    using the default printing routine.
  1007.  *
  1008.  * Results:
  1009.  *      None.
  1010.  *
  1011.  * Side effects:
  1012.  *    None.
  1013.  *
  1014.  * ----------------------------------------------------------------------------
  1015.  */
  1016.  
  1017. void
  1018. Mem_PrintConfig()
  1019. {
  1020.     Mem_PrintConfigSubr(memPrintProc, memPrintData);
  1021. }
  1022.  
  1023. /*
  1024.  * ----------------------------------------------------------------------------
  1025.  *
  1026.  * Mem_PrintConfigSubr --
  1027.  *
  1028.  *      Uses a client-supplied procedure to print out the exact
  1029.  *    configuration of the dynamic memory allocator.
  1030.  *
  1031.  * Results:
  1032.  *      None.
  1033.  *
  1034.  * Side effects:
  1035.  *      Stuff gets printed (?) by passing it to printProc.  See the
  1036.  *    documentation in Mem_PrintStatsSubr for the calling sequence to
  1037.  *    printProc.
  1038.  *
  1039.  * ----------------------------------------------------------------------------
  1040.  */
  1041.  
  1042. ENTRY void
  1043. Mem_PrintConfigSubr(printProc, clientData)
  1044.     void (*printProc)();    /* Procedure to actually print stuff. */
  1045.     ClientData clientData;    /* Argument to pass to printProc. */
  1046. {
  1047.     register Address ptr;
  1048. #ifdef VERBOSE
  1049.     int i, j;
  1050. #endif /* VERBOSE */
  1051.  
  1052.     LOCK_MONITOR;
  1053.  
  1054.     if (!initialized) {
  1055.     (*printProc)(clientData, "Allocator not initialized yet.\n");
  1056.     return;
  1057.     }
  1058.  
  1059. #ifdef VERBOSE
  1060.     (*printProc)(clientData, "Small object allocator:\n");
  1061.     for (i = 2; i < BIN_BUCKETS; i++) {
  1062.     if (freeLists[i] == (Address) NIL) {
  1063.         continue;
  1064.     }
  1065.     (*printProc)(clientData, "    %d bytes:", i*GRANULARITY);
  1066.     j = 5;
  1067.     for (ptr = freeLists[i]; ptr != (Address) NIL;
  1068.         ptr = (Address) GET_ADMIN(ptr)) {
  1069.         if (j == 5) {
  1070.         (*printProc)(clientData, "\n    ");
  1071.         j = 0;
  1072.         } else {
  1073.         j += 1;
  1074.         }
  1075.         (*printProc)(clientData, "%12#x", ptr);
  1076.     }
  1077.     (*printProc)(clientData, "\n");
  1078.     }
  1079. #endif /* VERBOSE */
  1080.  
  1081.     (*printProc)(clientData, "Large object allocator:\n");
  1082.  
  1083. #ifdef MEM_TRACE
  1084.     (*printProc)(clientData, "    Location   Orig. Size   State\n");
  1085. #else
  1086.     (*printProc)(clientData, "    Location       Size     State\n");
  1087. #endif /* MEM_TRACE */
  1088.  
  1089.     for (ptr = first + SIZE(GET_ADMIN(first)); ptr != last;
  1090.         ptr += SIZE(GET_ADMIN(ptr))) {
  1091.  
  1092. #ifdef MEM_TRACE
  1093.     (*printProc)(clientData, "%12#x %10d", ptr, GET_ORIG_SIZE(ptr));
  1094.     if (IS_DUMMY(GET_ADMIN(ptr))) {
  1095.         (*printProc)(clientData, "     Dummy\n");
  1096.     } else if (IS_IN_USE(GET_ADMIN(ptr))) {
  1097.         (*printProc)(clientData, "     In use (PC=0x%x)\n", GET_PC(ptr));
  1098. #else
  1099.     (*printProc)(clientData, "%12#x %10d", ptr, SIZE(GET_ADMIN(ptr)));
  1100.     if (IS_DUMMY(GET_ADMIN(ptr))) {
  1101.         (*printProc)(clientData, "     Dummy\n");
  1102.     } else if (IS_IN_USE(GET_ADMIN(ptr))) {
  1103.         (*printProc)(clientData, "     In use\n");
  1104. #endif /* MEM_TRACE */
  1105.     } else {
  1106.         (*printProc)(clientData, "     Free\n");
  1107.     }
  1108.     }
  1109.     UNLOCK_MONITOR;
  1110. }
  1111.  
  1112. /*
  1113.  * ----------------------------------------------------------------------------
  1114.  *
  1115.  * Mem_PrintInUse --
  1116.  *
  1117.  *      Uses a default procedure to print out the blocks in allocator
  1118.  *    that are still in use. The original size and the PC of the
  1119.  *    call to Mem_Alloc are printed.
  1120.  *
  1121.  * Results:
  1122.  *      None.
  1123.  *
  1124.  * Side effects:
  1125.  *      Stuff gets printed (?) by passing it to memPrintProc.  See the
  1126.  *    documentation in Mem_PrintStatsSubr for the calling sequence to
  1127.  *    memPrintProc.
  1128.  *
  1129.  * ----------------------------------------------------------------------------
  1130.  */
  1131.  
  1132. ENTRY void
  1133. Mem_PrintInUse()
  1134. {
  1135. #ifdef MEM_TRACE
  1136.     register Address ptr;
  1137.  
  1138.     LOCK_MONITOR;
  1139.  
  1140.     if (!initialized) {
  1141.     (*memPrintProc)(memPrintData, "Allocator not initialized yet.\n");
  1142.     return;
  1143.     }
  1144.  
  1145.     (*memPrintProc)(memPrintData, "Large objects still in use:\n");
  1146.     (*memPrintProc)(memPrintData, "    Location   Orig. Size   Alloc.PC\n");
  1147.  
  1148.     for (ptr = first + SIZE(GET_ADMIN(first)); ptr != last;
  1149.         ptr += SIZE(GET_ADMIN(ptr))) {
  1150.  
  1151.     if (!IS_DUMMY(GET_ADMIN(ptr)) && IS_IN_USE(GET_ADMIN(ptr))) {
  1152.         (*memPrintProc)(memPrintData,"%12#x %10d %12#x\n",
  1153.         ptr, GET_ORIG_SIZE(ptr), GET_PC(ptr));
  1154.     }
  1155.     }
  1156.     UNLOCK_MONITOR;
  1157. #endif /* MEM_TRACE */
  1158. }
  1159.  
  1160. /*
  1161.  *----------------------------------------------------------------------
  1162.  *
  1163.  * Mem_SetTraceSizes --
  1164.  *
  1165.  *    Defines a list of sizes to trace and causes tracing to start.
  1166.  *    If the numSizes is zero or the array ptr is NULL, tracing is
  1167.  *    turned off.
  1168.  *
  1169.  * Results:
  1170.  *    None.
  1171.  *
  1172.  * Side effects:
  1173.  *    Traces of Mem_Alloc and Mem_Free start or end.
  1174.  *
  1175.  *----------------------------------------------------------------------
  1176.  */
  1177. /*ARGSUSED*/
  1178. ENTRY void
  1179. Mem_SetTraceSizes(numSizes, arrayPtr)
  1180.     int          numSizes;        /* # of elements in arrayPtr */
  1181.     Mem_TraceInfo *arrayPtr;        /* Array of block sizes to trace. */
  1182. {
  1183. #ifdef MEM_TRACE
  1184.     int    i;
  1185.  
  1186.     LOCK_MONITOR;
  1187.  
  1188.     if (numSizes <= 0 || arrayPtr == (Mem_TraceInfo *)NIL ||
  1189.     arrayPtr == (Mem_TraceInfo *)NULL) {
  1190.     if (numSizes == -1) {
  1191.         numSizesToTrace = -1;
  1192.     } else {
  1193.         numSizesToTrace = 0;
  1194.     }
  1195.     UNLOCK_MONITOR;
  1196.     return;
  1197.     }
  1198.  
  1199.     if (numSizes > MAX_NUM_TRACE_SIZES) {
  1200.     numSizes = MAX_NUM_TRACE_SIZES;
  1201.     }
  1202.     numSizesToTrace = numSizes;
  1203.     for (i = 0; i < numSizes; i++) {
  1204.     sizeTraceArray[i].traceInfo = arrayPtr[i];
  1205.     sizeTraceArray[i].traceInfo.flags |= MEM_TRACE_NOT_INIT;
  1206.     }
  1207.     UNLOCK_MONITOR;
  1208.  
  1209. #endif /* MEM_TRACE */
  1210. }
  1211.  
  1212.  
  1213. /*
  1214.  *----------------------------------------------------------------------
  1215.  *
  1216.  * Mem_SetPrintProc --
  1217.  *
  1218.  *    Changes the default printing routines
  1219.  *
  1220.  * Results:
  1221.  *    None.
  1222.  *
  1223.  * Side effects:
  1224.  *    The default printing routine is changed.
  1225.  *
  1226.  *----------------------------------------------------------------------
  1227.  */
  1228.  
  1229. ENTRY void
  1230. Mem_SetPrintProc(proc, data)
  1231.     void    (*proc)();        /* Address of new print routine. */
  1232.     ClientData    data;        /* Data to be passed to proc. */
  1233. {
  1234.     LOCK_MONITOR;
  1235.     if (proc != (void(*)())NIL &&
  1236.         proc != (void(*)()) NULL) {
  1237.     memPrintProc = proc;
  1238.     memPrintData = data;
  1239.     }
  1240.     UNLOCK_MONITOR;
  1241. }
  1242.  
  1243. /*
  1244.  * ----------------------------------------------------------------------------
  1245.  *
  1246.  * Mem_PrintStatsSubrInt --
  1247.  *
  1248.  *      This procedure prints out statistics about memory allocation
  1249.  *    so far.
  1250.  *
  1251.  * Results:
  1252.  *      None.
  1253.  *
  1254.  * Side effects:
  1255.  *      The procedure printProc is called several times to print out
  1256.  *    information.  Its calling sequence is:
  1257.  *
  1258.  *    void
  1259.  *    printProc(clientData, format, arg1, arg2, arg3, arg4, arg5)
  1260.  *        ClientData clientData;
  1261.  *        char *format;
  1262.  *
  1263.  *    This is identical to the calling sequence for the standard I/o
  1264.  *    routine Io_Print.  The first argument is the clientData argument
  1265.  *    passed to this procedure, which need not necessarily be a
  1266.  *    (Io_Stream *).  There will never be more than 5 arguments.
  1267.  *    A typical calling sequence is:
  1268.  *    "Mem_PrintStatsSubr(Io_PrintStream, (ClientData) io_StdOut,
  1269.  *                50, 100, 1000)".
  1270.  *
  1271.  * ----------------------------------------------------------------------------
  1272.  */
  1273. INTERNAL void
  1274. Mem_PrintStatsSubrInt(printProc, clientData, smallMinNum, largeMinNum,
  1275.     largeMaxSize)
  1276.     void     (*printProc)();    /* Procedure to actually print stuff. */
  1277.     ClientData    clientData;    /* Argument to pass to printProc. */
  1278.     int        smallMinNum;    /* Minimum number of elements in a bucket
  1279.                  * before will print out stats. */
  1280.     int        largeMinNum;    /* Minimum number of large objects of a given
  1281.                  * size before will print out stats about
  1282.                  * the size. */
  1283.     int        largeMaxSize;    /* Statistics will be printed about all blocks
  1284.                  * over size regardless of how many there are*/
  1285. {
  1286.     register Address    ptr;
  1287.     register int    i;
  1288.     int        totalBlocks, totalAllocs, totalFree;
  1289.     int        allocBytes = 0;
  1290.     int        freeBytes = 0;
  1291.     Boolean    firstTime = TRUE;
  1292.     Boolean    warnedAboutOverflow;
  1293.  
  1294.     if (!initialized) {
  1295.     (*printProc)(clientData, "Allocator not initialized yet.\n");
  1296.     return;
  1297.     }
  1298.  
  1299.     (*printProc)(clientData, "\nTotal allocs = %d, frees = %d\n\n",
  1300.         mem_NumAllocs, mem_NumFrees);
  1301.  
  1302.     (*printProc)(clientData, "Small object allocator:\n");
  1303.     totalBlocks = totalAllocs = totalFree = 0;
  1304.     for (i = 2; i < BIN_BUCKETS; i++) {
  1305.     int    numFree = 0;
  1306.  
  1307.     if (numBlocks[i] <= 0) {
  1308.         continue;
  1309.     }
  1310.     allocBytes += numBlocks[i] * INDEX_TO_BLOCKSIZE(i);
  1311.     for (ptr = freeLists[i];
  1312.          ptr != (Address) NIL;
  1313.          ptr = (Address) GET_ADMIN(ptr)) {
  1314.  
  1315.         freeBytes += INDEX_TO_BLOCKSIZE(i);
  1316.         numFree += 1;
  1317.     }
  1318.     if (numBlocks[i] >= smallMinNum) {
  1319.         if (firstTime) {
  1320.         (*printProc)(clientData,
  1321.                 "    Size     Total    Allocs    In Use\n");
  1322.         firstTime = FALSE;
  1323.         }
  1324.         (*printProc)(clientData, "%8d%10d%10d%10d\n",
  1325.             INDEX_TO_BLOCKSIZE(i), numBlocks[i],
  1326.             numAllocs[i], numBlocks[i] - numFree);
  1327.     }
  1328.     totalBlocks += numBlocks[i];
  1329.     totalAllocs += numAllocs[i];
  1330.     totalFree += numFree;
  1331.     }
  1332.     (*printProc)(clientData, "   Total%10d%10d%10d\n", totalBlocks,
  1333.         totalAllocs, totalBlocks - totalFree);
  1334.     (*printProc)(clientData, "Bytes allocated = %d, freed = %d\n\n",
  1335.                 allocBytes, freeBytes);
  1336.  
  1337.     /*
  1338.      * Initialize the largest N-sizes buffer.
  1339.      */
  1340.     for (i = 0; i < MAX_TO_PRINT + 1; i++) {
  1341.     topN[i].size = -1;
  1342.     topN[i].free = 0;
  1343.     topN[i].dummy = 0;
  1344.     }
  1345.  
  1346.     warnedAboutOverflow = FALSE;
  1347.     for (ptr = first + SIZE(GET_ADMIN(first));
  1348.      ptr != last;
  1349.      ptr += SIZE(GET_ADMIN(ptr))) {
  1350.  
  1351.     int    admin;
  1352.     int    size;
  1353.     Boolean    found;
  1354.  
  1355.     admin = GET_ADMIN(ptr);
  1356.     if (!IS_DUMMY(admin) && !IS_IN_USE(admin)) {
  1357.         freeBytes += SIZE(admin);
  1358.     }
  1359.  
  1360.     size = SIZE(admin);
  1361. #ifdef MEM_TRACE
  1362.     if (size - GET_ORIG_SIZE(ptr) < 4 &&
  1363.         size - GET_ORIG_SIZE(ptr) >= 0) {
  1364.         size = GET_ORIG_SIZE(ptr);
  1365.     }
  1366. #endif /* MEM_TRACE */
  1367.  
  1368.     found = FALSE;
  1369.     for (i = 0; i < MAX_TO_PRINT; i++) {
  1370.         if (size == topN[i].size) {
  1371.         found = TRUE;
  1372.         topN[i].num++;
  1373.         if (IS_DUMMY(admin)) {
  1374.             topN[i].dummy++;
  1375.         } else if (IS_IN_USE(admin)) {
  1376.             topN[i].inUse++;
  1377.         } else {
  1378.             topN[i].free++;
  1379.         }
  1380.         break;
  1381.         } else if (topN[i].size == -1) {
  1382.         found = TRUE;
  1383.         topN[i].size = size;
  1384.         topN[i].num = 1;
  1385.         if (IS_DUMMY(admin)) {
  1386.             topN[i].dummy = 1;
  1387.         } else if (IS_IN_USE(admin)) {
  1388.             topN[i].inUse = 1;
  1389.         } else {
  1390.             topN[i].free = 1;
  1391.         }
  1392.         break;
  1393.         }
  1394.     }
  1395.  
  1396.     if (!found && !warnedAboutOverflow) {
  1397.         (*printProc)(clientData, "Largest-Size buffer overflow: %d\n",size);
  1398.         warnedAboutOverflow = TRUE;
  1399.     }
  1400.     }
  1401.     (*printProc)(clientData, "Large object allocator:\n");
  1402.     (*printProc)(clientData, "   Total bytes managed: %d\n", numLargeBytes);
  1403.     (*printProc)(clientData, "   Bytes in use:        %d\n",
  1404.                         numLargeBytes - freeBytes);
  1405.     firstTime = TRUE;
  1406.     for (i = 0; topN[i].size != -1; i++) {
  1407.     if ((topN[i].num >= largeMinNum || topN[i].size >= largeMaxSize) &&
  1408.         (topN[i].num != topN[i].dummy)) {
  1409.         if (firstTime) {
  1410.         (*printProc)(clientData, "%10s%10s%10s%10s\n",
  1411. #ifdef MEM_TRACE
  1412.             "Orig. Size", "Num", "Free", "In Use");
  1413. #else
  1414.             "Size", "Num", "Free", "In Use");
  1415. #endif /* MEM_TRACE */
  1416.         firstTime = FALSE;
  1417.         }
  1418.         (*printProc)(clientData, "%10d%10d%10d%10d\n",
  1419.         topN[i].size, topN[i].num, topN[i].free, topN[i].inUse);
  1420.     }
  1421.     }
  1422.     (*printProc)(clientData, "\n");
  1423. }
  1424.  
  1425. /*
  1426.  *----------------------------------------------------------------------
  1427.  *
  1428.  * DoTrace --
  1429.  *
  1430.  *    Print and/or store a trace record.
  1431.  *
  1432.  * Results:
  1433.  *    None.
  1434.  *
  1435.  * Side effects:
  1436.  *    None.
  1437.  *
  1438.  *----------------------------------------------------------------------
  1439.  */
  1440. #ifdef MEM_TRACE
  1441. INTERNAL static void
  1442. DoTrace(allocated, infoPtr, curPC, size)
  1443.     Boolean        allocated;    /* If TRUE, we are called by Mem_Alloc,
  1444.                      * otherwise by Mem_Free. */
  1445.     register Address    infoPtr;    /* Address of admin. info. */
  1446.     Address        curPC;        /* If called by Mem_Free, PC of
  1447.                      * call to Mem_Free, NULL otherwise. */
  1448.     int            size;        /* Size actually allocated. */
  1449. {
  1450.     int                    i, j;
  1451.     int                    origSize;
  1452.     Address                callerPC;
  1453.     register    struct    TraceElement    *trPtr;
  1454.  
  1455.     if (numSizesToTrace == -1) {
  1456.     PrintTrace(allocated, infoPtr, curPC);
  1457.     return;
  1458.     }
  1459.  
  1460.     callerPC = GET_PC(infoPtr);
  1461.  
  1462.     origSize = GET_ORIG_SIZE(infoPtr);
  1463.  
  1464.     for (i = 0, trPtr = sizeTraceArray; i < numSizesToTrace; i++, trPtr++) {
  1465.     if (trPtr->traceInfo.flags & MEM_DONT_USE_ORIG_SIZE) {
  1466.         if (trPtr->traceInfo.size != size) {
  1467.         continue;
  1468.         }
  1469.     } else if (trPtr->traceInfo.size != origSize) {
  1470.         continue;
  1471.     }
  1472.     if (trPtr->traceInfo.flags & MEM_PRINT_TRACE) {
  1473.         PrintTrace(allocated, infoPtr, curPC);
  1474.     }
  1475.     if (trPtr->traceInfo.flags & MEM_STORE_TRACE) {
  1476.         register int slot;
  1477.         if (trPtr->traceInfo.flags & MEM_TRACE_NOT_INIT) {
  1478.         for (j = 0; j < MAX_CALLERS_TO_TRACE; j++) {
  1479.             trPtr->allocInfo[j].numBlocks = 0;
  1480.             trPtr->allocInfo[j].callerPC = 0;
  1481.         }
  1482.         trPtr->traceInfo.flags &= ~MEM_TRACE_NOT_INIT;
  1483.         }
  1484.         slot = -1;
  1485.         for (j = 0; j < MAX_CALLERS_TO_TRACE; j++) {
  1486.         if (trPtr->allocInfo[j].callerPC == callerPC) {
  1487.             if (allocated) {
  1488.             trPtr->allocInfo[j].numBlocks++;
  1489.             } else {
  1490.             trPtr->allocInfo[j].numBlocks--;
  1491.             }
  1492.             return;
  1493.         }
  1494.         if ((trPtr->allocInfo[j].numBlocks == 0) && (slot < 0)) {
  1495.             slot = j;
  1496.         }
  1497.         }
  1498.         if ((slot >= 0) && allocated) {
  1499.         trPtr->allocInfo[slot].callerPC = callerPC;
  1500.         trPtr->allocInfo[slot].numBlocks = 1;
  1501.         }
  1502.     }
  1503.     return;
  1504.     }
  1505.     if (size > BIN_SIZE && mem_PrintLargeAllocPC) {
  1506.     printf("malloc(%d[%d]) from PC 0x%x\n", origSize, size, callerPC);
  1507.     }
  1508. }
  1509. #endif /* MEM_TRACE */
  1510.  
  1511.  
  1512.  
  1513. /*
  1514.  *----------------------------------------------------------------------
  1515.  *
  1516.  * Mem_DumpTrace --
  1517.  *
  1518.  *    Dump the allocation trace records for the given size block.  If
  1519.  *    the size is specified as -1 then all trace records for all size
  1520.  *    blocks are dumped.
  1521.  *
  1522.  * Results:
  1523.  *    None.
  1524.  *
  1525.  * Side effects:
  1526.  *    None.
  1527.  *
  1528.  *----------------------------------------------------------------------
  1529.  */
  1530. /*ARGSUSED*/
  1531. void
  1532. Mem_DumpTrace(blockSize)
  1533.     int    blockSize;
  1534. {
  1535. #ifdef MEM_TRACE
  1536.     register    struct    TraceElement    *trPtr;
  1537.     int                    i, j;
  1538.  
  1539.     for (i = 0, trPtr = sizeTraceArray; i < numSizesToTrace; i++, trPtr++) {
  1540.     if (trPtr->traceInfo.size != blockSize && blockSize != -1) {
  1541.         continue;
  1542.     }
  1543.     if (!(trPtr->traceInfo.flags & MEM_STORE_TRACE) ||
  1544.         (trPtr->traceInfo.flags & MEM_TRACE_NOT_INIT)) {
  1545.         continue;
  1546.     }
  1547.  
  1548.     if (trPtr->traceInfo.flags & MEM_DONT_USE_ORIG_SIZE) {
  1549.         (*memPrintProc)(memPrintData, "Trace for block size = %d:\n",
  1550.                       trPtr->traceInfo.size);
  1551.     } else {
  1552.         (*memPrintProc)(memPrintData, "Trace for size = %d (%d):\n",
  1553.                   trPtr->traceInfo.size,
  1554.                   BYTES_TO_BLOCKSIZE(trPtr->traceInfo.size));
  1555.     }
  1556.     (*memPrintProc)(memPrintData, "Caller-PC      Num-blocks  \n");
  1557.     for (j = 0; j < MAX_CALLERS_TO_TRACE; j++) {
  1558.         if (trPtr->allocInfo[j].numBlocks == 0) {
  1559.         break;
  1560.         }
  1561.         (*memPrintProc)(memPrintData, "%8x         %6d\n",
  1562.                       trPtr->allocInfo[j].callerPC,
  1563.                       trPtr->allocInfo[j].numBlocks);
  1564.     }
  1565.     if  (blockSize != -1) {
  1566.         break;
  1567.     }
  1568.     }
  1569. #endif
  1570. }
  1571.  
  1572.  
  1573.  
  1574. /*
  1575.  *----------------------------------------------------------------------
  1576.  *
  1577.  * PrintTrace --
  1578.  *
  1579.  *    Print out the given trace information about a memory trace record.
  1580.  *
  1581.  * Results:
  1582.  *    None.
  1583.  *
  1584.  * Side effects:
  1585.  *    None.
  1586.  *
  1587.  *----------------------------------------------------------------------
  1588.  */
  1589. #ifdef MEM_TRACE
  1590. INTERNAL static void
  1591. PrintTrace(allocated, infoPtr, curPC)
  1592.     Boolean        allocated;    /* If TRUE, we are called by Mem_Alloc,
  1593.                      * otherwise by Mem_Free. */
  1594.     register Address    infoPtr;    /* Address of admin. info. */
  1595.     Address        curPC;        /* If called by Mem_Free, PC of
  1596.                      * call to Mem_Free, NULL otherwise. */
  1597. {
  1598.     if (allocated) {
  1599.     (*memPrintProc)(memPrintData,
  1600.         "Mem_Alloc: PC=0x%x  addr=0x%x  size=%d\n",
  1601.         GET_PC(infoPtr), infoPtr+sizeof(AdminInfo),
  1602.         GET_ORIG_SIZE(infoPtr));
  1603.     } else {
  1604.     (*memPrintProc)(memPrintData,
  1605.         "Mem_Free:  PC=0x%x  addr=0x%x  size=%d *\n",
  1606.         curPC, infoPtr+sizeof(AdminInfo), GET_ORIG_SIZE(infoPtr));
  1607.     }
  1608. }
  1609. #endif /* MEM_TRACE */
  1610.  
  1611.